Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos
| Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos |
| Autore | Murat Cecile |
| Pubbl/distr/stampa | London ; ; Newport Beach, CA, : ISTE, 2006 |
| Descrizione fisica | 1 online resource (269 p.) |
| Disciplina |
511.6
519.2 |
| Altri autori (Persone) | PaschosVangelis Th |
| Collana | ISTE |
| Soggetto topico |
Combinatorial probabilities
Combinatorial optimization Random graphs |
| Soggetto genere / forma | Electronic books. |
| ISBN |
1-280-51061-7
9786610510610 1-84704-483-2 0-470-39464-1 0-470-61250-9 1-84704-583-9 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Probabilistic Combinatorial Optimization on Graphs; Contents; Preface; Chapter 1. A Short Insight into Probabilistic Combinatorial Optimization; 1.1. Motivations and applications; 1.2. A formalism for probabilistic combinatorial optimization; 1.3. The main methodological issues dealing with probabilistic combinatorial optimization; 1.3.1. Complexity issues; 1.3.1.1. Membership in NPO is not always obvious; 1.3.1.2. Complexity of deterministic vs. complexity of probabilistic optimization problems; 1.3.2. Solution issues; 1.3.2.1. Characterization of optimal a priori solutions
1.3.2.2. Polynomial subcases1.3.2.3. Exact solutions and polynomial approximation issues; 1.4. Miscellaneous and bibliographic notes; First Part. Probabilistic Graph-Problems; Chapter 2. The Probabilistic Maximum Independent Set; 2.1. The modification strategies and a preliminary result; 2.1.1. Strategy M1; 2.1.2. Strategies M2 and M3; 2.1.3. Strategy M4; 2.1.4. Strategy M5; 2.1.5. A general mathematical formulation for the five functionals; 2.2. PROBABILISTIC MAX INDEPENDENT SET1; 2.2.1. Computing optimal a priori solutions; 2.2.2. Approximating optimal solutions 2.2.3. Dealing with bipartite graphs2.3. PROBABILISTIC MAX INDEPENDENT SET2 and 3; 2.3.1. Expressions for E(G, S, M2) and E(G, S, M3); 2.3.2. An upper bound for the complexity of E(G, S, M2); 2.3.3. Bounds for E(G, S, M2); 2.3.4. Approximating optimal solutions; 2.3.4.1. Using argmax {ΣviESpi} as an a priori solution; 2.3.4.2. Using approximations of MAX INDEPENDENT SET; 2.3.5. Dealing with bipartite graphs; 2.4. PROBABILISTIC MAX INDEPENDENT SET4; 2.4.1. An expression for E(G, S, M4); 2.4.2. Using S* or argmax{ΣviESpi} as an a priori solution; 2.4.3. Dealing with bipartite graphs 2.5. PROBABILISTIC MAX INDEPENDENT SET52.5.1. In general graphs; 2.5.2. In bipartite graphs; 2.6. Summary of the results; 2.7. Methodological questions; 2.7.1. Maximizing a criterion associated with gain; 2.7.1.1. The minimum gain criterion; 2.7.1.2. The maximum gain criterion; 2.7.2. Minimizing a criterion associated with regret; 2.7.2.1. The maximum regret criterion; 2.7.3. Optimizing expectation; 2.8. Proofs of the results; 2.8.1. Proof of Proposition 2.1; 2.8.2. Proof of Theorem 2.6; 2.8.3. Proof of Proposition 2.3; 2.8.4. Proof of Theorem 2.13 Chapter 3. The Probabilistic Minimum Vertex Cover3.1. The strategies M1, M2 and M3 and a general preliminary result; 3.1.1. Specification of M1, M2 and M3; 3.1.1.1. Strategy M1; 3.1.1.2. Strategy M2; 3.1.1.3. Strategy M3; 3.1.2. A first expression for the functionals; 3.2. PROBABILISTIC MIN VERTEX COVER1; 3.3. PROBABILISTIC MIN VERTEX COVER2; 3.4. PROBABILISTIC MIN VERTEX COVER3; 3.4.1. Building E(G, C, M3); 3.4.2. Bounds for E(G, C, M3); 3.5. Some methodological questions; 3.6. Proofs of the results; 3.6.1. Proof of Theorem 3.3; 3.6.2. On the the bounds obtained in Theorem 3.3 Chapter 4. The Probabilistic Longest Path |
| Record Nr. | UNINA-9910143315903321 |
Murat Cecile
|
||
| London ; ; Newport Beach, CA, : ISTE, 2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos
| Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos |
| Autore | Murat Cecile |
| Pubbl/distr/stampa | London ; ; Newport Beach, CA, : ISTE, 2006 |
| Descrizione fisica | 1 online resource (269 p.) |
| Disciplina |
511.6
519.2 |
| Altri autori (Persone) | PaschosVangelis Th |
| Collana | ISTE |
| Soggetto topico |
Combinatorial probabilities
Combinatorial optimization Random graphs |
| ISBN |
1-280-51061-7
9786610510610 1-84704-483-2 0-470-39464-1 0-470-61250-9 1-84704-583-9 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Probabilistic Combinatorial Optimization on Graphs; Contents; Preface; Chapter 1. A Short Insight into Probabilistic Combinatorial Optimization; 1.1. Motivations and applications; 1.2. A formalism for probabilistic combinatorial optimization; 1.3. The main methodological issues dealing with probabilistic combinatorial optimization; 1.3.1. Complexity issues; 1.3.1.1. Membership in NPO is not always obvious; 1.3.1.2. Complexity of deterministic vs. complexity of probabilistic optimization problems; 1.3.2. Solution issues; 1.3.2.1. Characterization of optimal a priori solutions
1.3.2.2. Polynomial subcases1.3.2.3. Exact solutions and polynomial approximation issues; 1.4. Miscellaneous and bibliographic notes; First Part. Probabilistic Graph-Problems; Chapter 2. The Probabilistic Maximum Independent Set; 2.1. The modification strategies and a preliminary result; 2.1.1. Strategy M1; 2.1.2. Strategies M2 and M3; 2.1.3. Strategy M4; 2.1.4. Strategy M5; 2.1.5. A general mathematical formulation for the five functionals; 2.2. PROBABILISTIC MAX INDEPENDENT SET1; 2.2.1. Computing optimal a priori solutions; 2.2.2. Approximating optimal solutions 2.2.3. Dealing with bipartite graphs2.3. PROBABILISTIC MAX INDEPENDENT SET2 and 3; 2.3.1. Expressions for E(G, S, M2) and E(G, S, M3); 2.3.2. An upper bound for the complexity of E(G, S, M2); 2.3.3. Bounds for E(G, S, M2); 2.3.4. Approximating optimal solutions; 2.3.4.1. Using argmax {ΣviESpi} as an a priori solution; 2.3.4.2. Using approximations of MAX INDEPENDENT SET; 2.3.5. Dealing with bipartite graphs; 2.4. PROBABILISTIC MAX INDEPENDENT SET4; 2.4.1. An expression for E(G, S, M4); 2.4.2. Using S* or argmax{ΣviESpi} as an a priori solution; 2.4.3. Dealing with bipartite graphs 2.5. PROBABILISTIC MAX INDEPENDENT SET52.5.1. In general graphs; 2.5.2. In bipartite graphs; 2.6. Summary of the results; 2.7. Methodological questions; 2.7.1. Maximizing a criterion associated with gain; 2.7.1.1. The minimum gain criterion; 2.7.1.2. The maximum gain criterion; 2.7.2. Minimizing a criterion associated with regret; 2.7.2.1. The maximum regret criterion; 2.7.3. Optimizing expectation; 2.8. Proofs of the results; 2.8.1. Proof of Proposition 2.1; 2.8.2. Proof of Theorem 2.6; 2.8.3. Proof of Proposition 2.3; 2.8.4. Proof of Theorem 2.13 Chapter 3. The Probabilistic Minimum Vertex Cover3.1. The strategies M1, M2 and M3 and a general preliminary result; 3.1.1. Specification of M1, M2 and M3; 3.1.1.1. Strategy M1; 3.1.1.2. Strategy M2; 3.1.1.3. Strategy M3; 3.1.2. A first expression for the functionals; 3.2. PROBABILISTIC MIN VERTEX COVER1; 3.3. PROBABILISTIC MIN VERTEX COVER2; 3.4. PROBABILISTIC MIN VERTEX COVER3; 3.4.1. Building E(G, C, M3); 3.4.2. Bounds for E(G, C, M3); 3.5. Some methodological questions; 3.6. Proofs of the results; 3.6.1. Proof of Theorem 3.3; 3.6.2. On the the bounds obtained in Theorem 3.3 Chapter 4. The Probabilistic Longest Path |
| Record Nr. | UNISA-996216942703316 |
|
Murat Cecile
|
||
| London ; ; Newport Beach, CA, : ISTE, 2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos
| Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos |
| Autore | Murat Cecile |
| Pubbl/distr/stampa | London ; ; Newport Beach, CA, : ISTE, 2006 |
| Descrizione fisica | 1 online resource (269 p.) |
| Disciplina |
511.6
519.2 |
| Altri autori (Persone) | PaschosVangelis Th |
| Collana | ISTE |
| Soggetto topico |
Combinatorial probabilities
Combinatorial optimization Random graphs |
| ISBN |
1-280-51061-7
9786610510610 1-84704-483-2 0-470-39464-1 0-470-61250-9 1-84704-583-9 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Probabilistic Combinatorial Optimization on Graphs; Contents; Preface; Chapter 1. A Short Insight into Probabilistic Combinatorial Optimization; 1.1. Motivations and applications; 1.2. A formalism for probabilistic combinatorial optimization; 1.3. The main methodological issues dealing with probabilistic combinatorial optimization; 1.3.1. Complexity issues; 1.3.1.1. Membership in NPO is not always obvious; 1.3.1.2. Complexity of deterministic vs. complexity of probabilistic optimization problems; 1.3.2. Solution issues; 1.3.2.1. Characterization of optimal a priori solutions
1.3.2.2. Polynomial subcases1.3.2.3. Exact solutions and polynomial approximation issues; 1.4. Miscellaneous and bibliographic notes; First Part. Probabilistic Graph-Problems; Chapter 2. The Probabilistic Maximum Independent Set; 2.1. The modification strategies and a preliminary result; 2.1.1. Strategy M1; 2.1.2. Strategies M2 and M3; 2.1.3. Strategy M4; 2.1.4. Strategy M5; 2.1.5. A general mathematical formulation for the five functionals; 2.2. PROBABILISTIC MAX INDEPENDENT SET1; 2.2.1. Computing optimal a priori solutions; 2.2.2. Approximating optimal solutions 2.2.3. Dealing with bipartite graphs2.3. PROBABILISTIC MAX INDEPENDENT SET2 and 3; 2.3.1. Expressions for E(G, S, M2) and E(G, S, M3); 2.3.2. An upper bound for the complexity of E(G, S, M2); 2.3.3. Bounds for E(G, S, M2); 2.3.4. Approximating optimal solutions; 2.3.4.1. Using argmax {ΣviESpi} as an a priori solution; 2.3.4.2. Using approximations of MAX INDEPENDENT SET; 2.3.5. Dealing with bipartite graphs; 2.4. PROBABILISTIC MAX INDEPENDENT SET4; 2.4.1. An expression for E(G, S, M4); 2.4.2. Using S* or argmax{ΣviESpi} as an a priori solution; 2.4.3. Dealing with bipartite graphs 2.5. PROBABILISTIC MAX INDEPENDENT SET52.5.1. In general graphs; 2.5.2. In bipartite graphs; 2.6. Summary of the results; 2.7. Methodological questions; 2.7.1. Maximizing a criterion associated with gain; 2.7.1.1. The minimum gain criterion; 2.7.1.2. The maximum gain criterion; 2.7.2. Minimizing a criterion associated with regret; 2.7.2.1. The maximum regret criterion; 2.7.3. Optimizing expectation; 2.8. Proofs of the results; 2.8.1. Proof of Proposition 2.1; 2.8.2. Proof of Theorem 2.6; 2.8.3. Proof of Proposition 2.3; 2.8.4. Proof of Theorem 2.13 Chapter 3. The Probabilistic Minimum Vertex Cover3.1. The strategies M1, M2 and M3 and a general preliminary result; 3.1.1. Specification of M1, M2 and M3; 3.1.1.1. Strategy M1; 3.1.1.2. Strategy M2; 3.1.1.3. Strategy M3; 3.1.2. A first expression for the functionals; 3.2. PROBABILISTIC MIN VERTEX COVER1; 3.3. PROBABILISTIC MIN VERTEX COVER2; 3.4. PROBABILISTIC MIN VERTEX COVER3; 3.4.1. Building E(G, C, M3); 3.4.2. Bounds for E(G, C, M3); 3.5. Some methodological questions; 3.6. Proofs of the results; 3.6.1. Proof of Theorem 3.3; 3.6.2. On the the bounds obtained in Theorem 3.3 Chapter 4. The Probabilistic Longest Path |
| Record Nr. | UNINA-9910830041603321 |
|
Murat Cecile
|
||
| London ; ; Newport Beach, CA, : ISTE, 2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos
| Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos |
| Autore | Murat Cecile |
| Pubbl/distr/stampa | London ; ; Newport Beach, CA, : ISTE, 2006 |
| Descrizione fisica | 1 online resource (269 p.) |
| Disciplina |
511.6
519.2 |
| Altri autori (Persone) | PaschosVangelis Th |
| Collana | ISTE |
| Soggetto topico |
Combinatorial probabilities
Combinatorial optimization Random graphs |
| ISBN |
1-280-51061-7
9786610510610 1-84704-483-2 0-470-39464-1 0-470-61250-9 1-84704-583-9 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Probabilistic Combinatorial Optimization on Graphs; Contents; Preface; Chapter 1. A Short Insight into Probabilistic Combinatorial Optimization; 1.1. Motivations and applications; 1.2. A formalism for probabilistic combinatorial optimization; 1.3. The main methodological issues dealing with probabilistic combinatorial optimization; 1.3.1. Complexity issues; 1.3.1.1. Membership in NPO is not always obvious; 1.3.1.2. Complexity of deterministic vs. complexity of probabilistic optimization problems; 1.3.2. Solution issues; 1.3.2.1. Characterization of optimal a priori solutions
1.3.2.2. Polynomial subcases1.3.2.3. Exact solutions and polynomial approximation issues; 1.4. Miscellaneous and bibliographic notes; First Part. Probabilistic Graph-Problems; Chapter 2. The Probabilistic Maximum Independent Set; 2.1. The modification strategies and a preliminary result; 2.1.1. Strategy M1; 2.1.2. Strategies M2 and M3; 2.1.3. Strategy M4; 2.1.4. Strategy M5; 2.1.5. A general mathematical formulation for the five functionals; 2.2. PROBABILISTIC MAX INDEPENDENT SET1; 2.2.1. Computing optimal a priori solutions; 2.2.2. Approximating optimal solutions 2.2.3. Dealing with bipartite graphs2.3. PROBABILISTIC MAX INDEPENDENT SET2 and 3; 2.3.1. Expressions for E(G, S, M2) and E(G, S, M3); 2.3.2. An upper bound for the complexity of E(G, S, M2); 2.3.3. Bounds for E(G, S, M2); 2.3.4. Approximating optimal solutions; 2.3.4.1. Using argmax {ΣviESpi} as an a priori solution; 2.3.4.2. Using approximations of MAX INDEPENDENT SET; 2.3.5. Dealing with bipartite graphs; 2.4. PROBABILISTIC MAX INDEPENDENT SET4; 2.4.1. An expression for E(G, S, M4); 2.4.2. Using S* or argmax{ΣviESpi} as an a priori solution; 2.4.3. Dealing with bipartite graphs 2.5. PROBABILISTIC MAX INDEPENDENT SET52.5.1. In general graphs; 2.5.2. In bipartite graphs; 2.6. Summary of the results; 2.7. Methodological questions; 2.7.1. Maximizing a criterion associated with gain; 2.7.1.1. The minimum gain criterion; 2.7.1.2. The maximum gain criterion; 2.7.2. Minimizing a criterion associated with regret; 2.7.2.1. The maximum regret criterion; 2.7.3. Optimizing expectation; 2.8. Proofs of the results; 2.8.1. Proof of Proposition 2.1; 2.8.2. Proof of Theorem 2.6; 2.8.3. Proof of Proposition 2.3; 2.8.4. Proof of Theorem 2.13 Chapter 3. The Probabilistic Minimum Vertex Cover3.1. The strategies M1, M2 and M3 and a general preliminary result; 3.1.1. Specification of M1, M2 and M3; 3.1.1.1. Strategy M1; 3.1.1.2. Strategy M2; 3.1.1.3. Strategy M3; 3.1.2. A first expression for the functionals; 3.2. PROBABILISTIC MIN VERTEX COVER1; 3.3. PROBABILISTIC MIN VERTEX COVER2; 3.4. PROBABILISTIC MIN VERTEX COVER3; 3.4.1. Building E(G, C, M3); 3.4.2. Bounds for E(G, C, M3); 3.5. Some methodological questions; 3.6. Proofs of the results; 3.6.1. Proof of Theorem 3.3; 3.6.2. On the the bounds obtained in Theorem 3.3 Chapter 4. The Probabilistic Longest Path |
| Record Nr. | UNINA-9910841663103321 |
|
Murat Cecile
|
||
| London ; ; Newport Beach, CA, : ISTE, 2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||